#include<stdio.h>
/*memcpy useage*/
#include<string.h>
#include"GKoSon.h"
void swap_int(int *A,int *B)
{
	printf("INPUT %d --- %d  \n",*A,*B);
#if 0	
	int C=*A;
	*A=*B;
	*B=C;
#else
	*A=*A^*B;
	*B=*A^*B;
	*A=*A^*B;
#endif
	printf("OUTPUT %d --- %d  \n",*A,*B);
}

/*按照从小到大的方式排序*/
/*冒泡排序*/
void Sort_MaoPao(int *a,int len)
{
	int i=0,j=0;
	for(i=0;i<len;i++)
	 for(j=i+1;j<len;j++)
	  if(a[i]>a[j])
	  swap_int(&a[i],&a[j]);
	 /*Everytime MIN FIRST每次操作MIN置前*/
}


/*选择排序*/
/*查找数组a[len]从startindex开始到尾len的哪个成员MIN返回它的索引(后面有一个更强的函数)*/
int Find_ArrMinIndex(int *a,int len,int startindex)
{
	int i=startindex,j=startindex,MIN=a[startindex];
	for(;i<len;i++)
	{
		if(a[i]<MIN)
		{
			MIN=a[i];
			j=i;
		}
	}
	return j;
}
/*比冒泡稍微好一点的算法 在于不是每次都是目光短浅连续两者交换而是先找到MIN在交换 把MIN放到头部 此后不再干扰余下的Min*/
void Sort_XuanZe(int *a,int len)
{
	int i=0,j=0;
	for(i=0;i<len;i++)
	{
		j=Find_ArrMinIndex(a,len,i);
		swap_int(&a[i],&a[j]);
	}
}

/*插入排序*/
/*1个哨兵1个&&  2个循环2句话 3次tem*/
void Sort_ChaRu(int *a,int len)
{
	int i=0,tem=0;
	for(i=0;i<len;i++)
	{//1 2 4 5 -- 【3】  此时i=3
	    tem=a[i+1];
	    while(a[i]>tem&&i>=0)
	    {
		a[i+1]=a[i];
		i--;
 	    }
        a[i+1]=tem;	
	}
}

/*快速排序*/
void Sort_Quick(int *a,int start,int end)
{
	int i=start+1,j=end;
	if(start>=end)
	return;
	while(1)
	{
		for(;a[j]>a[start];j--);
	   	for(;a[i]<a[start];i++);
		if(i<j)
		 swap_int(&a[i],&a[j]);
		else
		 break;
	}
	swap_int(&a[start],&a[j]);
	Sort_Quick(a,start,j-1);
	Sort_Quick(a,j+1,end);
}


/*自己想的一个算法，每次找到MIN MAX分别丢到头尾，如此递归  没有快速排序好 因为别人减法 我每次都要找M值*/
/*这就是那个更强的函数 每次找到最值和最值的索引 全部给你*/
//typedef	struct
//	{
//		int Min;
//		int Minindex;
//		int Max;
//		int Maxindex;
//	}ArrPeak;

	
void Show_ArrPeak(ArrPeak arrpeak)	
{
	printf("%d-%d-%d-%d\n",arrpeak.Min,arrpeak.Minindex,arrpeak.Max,arrpeak.Maxindex);
}
ArrPeak Get_ArrPeak(const int *a,int len)
{
	int i=0,j=0;
	ArrPeak ack={a[0],0,a[0],0};
	for(i=0;i<len;i++)
	{
		if(a[i]>ack.Max)
		{
			ack.Max=a[i];
			ack.Maxindex=i;
		}
		else if(a[i]<ack.Min)
		{
			ack.Min=a[i];
			ack.Minindex=i;
		}
	}
	return ack;
}	
/*很快完成我的函数，我的思路很明确，但是测试出现问题 比如5 3 4这样的 5 4 3交换的时候重叠，前面的交换影响了后面的*/
/*怎么办？方案1我的问题就是前面的交换影响了后面，用if挑出来，这种情况特殊处理*/
/*方案2问题的根源是交换以后影响了最值，比如5 3 4找到最小的3角标是1 你交换了角标0-1也就是5-3 然后你找到的最大是5角标是0 你在交换角标0-2交换的是3-4根上解决问题是交换以后再次Find*/
#if 0
void Sort_XuanZeandQuick(int *a,int len)/*失败*/
{

	ArrPeak arrpeak={0};
	if(len<2)
	return;
	arrpeak=Get_ArrPeak(a,len);
	swap_int(&a[len-1],&a[arrpeak.Maxindex]);
	swap_int(&a[0],&a[arrpeak.Minindex]);//MIN TO FIRST MUST IN THE END 5 3 4//5 4 3
	Sort_XuanZeandQuick((a+1),(len-2));
}
#endif

#if 0/*方案1*/
void Sort_XuanZeandQuick(int *a,int len)/*成功*/
{

	ArrPeak arrpeak={0};
	if(len<2)
	return;
	arrpeak=Get_ArrPeak(a,len);
	if(arrpeak.Maxindex==0&&arrpeak.Minindex==(len-1))
		swap_int(&a[0],&a[arrpeak.Minindex]);
	else if(arrpeak.Maxindex==0)
		{
		swap_int(&a[len-1],&a[arrpeak.Maxindex]);
		swap_int(&a[0],&a[arrpeak.Minindex]);
		}
	else
		{	
		swap_int(&a[0],&a[arrpeak.Minindex]);
		swap_int(&a[len-1],&a[arrpeak.Maxindex]);
		}
	Sort_XuanZeandQuick((a+1),(len-2));
}
#else/*方案2*/
void Sort_XuanZeandQuick(int *a,int len)
{

	ArrPeak arrpeak={0};
	if(len<2)
	return;
	arrpeak=Get_ArrPeak(a,len);
	swap_int(&a[0],&a[arrpeak.Minindex]);
	arrpeak=Get_ArrPeak(a,len);
	swap_int(&a[len-1],&a[arrpeak.Maxindex]);		
	Sort_XuanZeandQuick((a+1),(len-2));
}
#endif


/*打印数组*/
void show(int *arr,int len)
{
	int i=0;for(i=0;i<len;i++)printf("%d ",arr[i]);printf("\n");
}

/*数组交换 默认是a[6]*/
void Swap_Arr(int *a,int *b)
{
	int c[6]={0};
	memcpy(c,a,6*sizeof(int));//why 5 wrong?
	memcpy(a,b,6*sizeof(int));
	memcpy(b,c,6*sizeof(int));
}

/*直接照搬快速排序 改为二维数组的 注意二维数组的传参int (*arr)[6]是二位数组 每一行都是a[6]这样的*/
void Sort_QuickTwoWei(int (*arr)[6],int start,int end)
{
	int i=start+1,j=end;
	if(start>=end)
	return;
	while(1)
	{
	for(;arr[j][5]>arr[start][5];j--);//3-->#dfine
	for(;arr[i][5]<arr[start][5];i++);
	if(i<j)
	Swap_Arr(arr[i],arr[j]);
	else
	break;
	}
	Swap_Arr(arr[start],arr[j]);
	Sort_QuickTwoWei(arr,0,j-1);
	Sort_QuickTwoWei(arr,j+1,end);
}

/*直接照搬选择排序 改为二维数组的 */
void Sort_XuanZeTwoWei(int (*arr)[6],int len)
{
int i=0,j=0,t=0,Min=0;
for(i=0;i<len;i++)
 {
	Min=arr[i][5];//need update
	
	for(j=i,t=i;j<len;j++)
	if(arr[j][5]<Min)
	{
	Min=arr[j][5];
	t=j;	
	}
	if(t!=i)
	Swap_Arr(arr[i],arr[t]);
 }
}

void Print_TwoWei(int (*arr)[6])
{
	#if 0/*这就是直接打印二维数组*/
	int i=0,j=0;
	for(i=0;i<5;i++,printf("\n"))
	 for(j=0;j<6;j++)
	 printf("%d ",arr[i][j]);
	#else/*前面的函数是真的在排序二维数组 能不能只是打印的时候排序输出呢？简单点的 写一个标记数组 一旦输出过就不在输出即可 根据第5列大小输出*/
	int flag[5]={0},Min=arr[0][5];
	int i=0,j=0,t=0;
	for(i=0;i<5;i++,printf("\n"))
	 {
		Min=arr[0][5]+arr[1][5]+arr[2][5]+arr[3][5]+arr[4][5];/*必须每次进来初始化给Min一个特别大的数据 我用SUM举例子罢了Fist GIve big big num!*/
		for(j=0;j<5;j++)
		if(arr[j][5]<Min&&flag[j]==0)
		{	
		Min=arr[j][5];
		t=j;
		}	
		show(arr[t],6);
		flag[t]=1;
	 }
#endif
}
